package com.zp.self.module.level_4_算法练习.算法.排序;

import org.junit.Test;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author By ZengPeng
 */
public class VI_快速排序_O_nXlogn__nXn {
    @Test
    public void main() {
        int[] arr = new int[]{4,7,2,3,432,334,2,1,23,23,33,32,23,34552};
        quicklySingle(arr);
        for (int i : arr)  System.out.print(i + ",");
    }

    /**
     题目： 快速排序：时间：O(n*n--n*logn) 、空间：O(logn)、顺序不稳定

     分析：快速排序 -- 单边 --转换为非递归--栈
                      每次start = left 开始,记录小于基准值的个数，并移动到左边， 交换位置，其实就是下标记录
                      然后再递归 [left ,start-1] ,[start+1,right]
     **/
    private static void quicklyStack(int[] arr) {
        Stack<int[]> stack = new Stack<>();
        stack.add(new int[]{0,arr.length-1});
        while (!stack.isEmpty()){
            int[] pop = stack.pop();
            if(pop[0]>=pop[1]) return;
            int start = pop[0],mark =start,point = arr[start],right=pop[1];
            while (start<=right){
                if(arr[start]<point){
                    arr[start] = arr[start]^arr[mark];
                    arr[mark] = arr[start]^arr[mark];
                    arr[start] = arr[start]^arr[mark];
                    mark++;
                }
                start++;
            }
            stack.add(new int[]{pop[0],mark-1});
            stack.add(new int[]{mark+1,pop[1]});
        }
    }

    /**
     * Description: 快速排序 -- 单边
     *                  每次start = left 开始,记录小于基准值的个数，并移动到左边， 交换位置，其实就是下标记录
     *                  然后再递归 [left ,start-1] ,[start+1,right]
     */
    private static void quicklySingle(int[] arr) {
        dfsSingle(arr,0,arr.length-1);
    }
    //不断遍历，找出小于基准值的元素，移动到标记下标出，标记下标++.
    //[left,mark-1] 则是小于基准值的  ，[mark，right]是大于基准值的
    private static void dfsSingle(int[] arr, int left, int right) {
        if(left>=right) return;
        int mark =left,index = left+1,point = arr[left];
        while (index<=right){
            if(arr[index]<point && ++mark !=index){
                arr[index] = arr[index]^arr[mark];
                arr[mark] = arr[index]^arr[mark];
                arr[index] = arr[index]^arr[mark];
            }
            index++;
        }
        arr[left] = arr[mark];
        arr[mark] = point;
        dfsSingle(arr,left,mark-1);
        dfsSingle(arr,mark+1,right);
    }
    /**
     题目：快速排序

     分析：
         1.找个分叉节点 P【以左1为例子】,将arr[i] < P 的数放在左边,将arr[i] > P 的数放在右边.
         2.因为找了左1 arr[0]为对比点，所以arr[0]空出来了【称L空】.
             先【从右】不断right--,找arr[right] < P的值放到L[空],此时arr[right]就空出来了
             在【从左】不断left++,找arr[left] < P的值放到arr[right],此时arr[left]就空出来了
         3.当left ==  right 时， arr[left] = P.此时，左边小于P,右边大于P.
         4.循环上面3个步骤

     疑问：
         1.时间复杂度为什么是 O(n*logn)?
             因为减少了 部分比较 。
             如： 1 、2、 3  ，2<3，就不会比较1与3了,以及交互数据位置
     **/
    private void myQuickSort(int[] arr) {
        myQuickSort(arr,0,arr.length-1);
    }

    private void myQuickSort(int[] arr, int left, int right) {
        if(left>=right) return;
        int nLeft = left,nRight=right;
        int referPoint = arr[left];
        while (nLeft!=nRight){
            //这里arr[nRight]==referPoint 为什么要跳过？ 因为：等于分叉值的放在左边，下一次左区域递归会移到最右边的. 右边的同理。
            while (arr[nRight]>=referPoint && nRight>nLeft)//【从右】不断right--,找arr[right] < P的值放到L[空],此时arr[right]就空出来了
                nRight--;
            arr[nLeft] = arr[nRight];//这里要找到了才会替换吧？ 非也 ：当nRight == nLeft 时，跳出也交换一次不会出问题。

            while (arr[nLeft]<=referPoint && nRight>nLeft)//【从左】不断left++,找arr[left] < P的值放到arr[right],此时arr[left]就空出来了
                nLeft++;
            arr[nRight] = arr[nLeft];
        }
        arr[nLeft] = referPoint;
        myQuickSort(arr,left,nLeft-1);//nLeft这个节点就拍好顺序了
        myQuickSort(arr,nRight+1,right);
    }
}
